package week_four;


public class LongestIncreasingPathInMatrix_DFS_329 {
    private int m, n;
    private int[][] ans;
    private int[] dx = {0, 1, 0, -1};
    private int[] dy = {1, 0, -1, 0};

    public int longestIncreasingPath(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        ans = new int[m][n];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans[i][j] = -1;
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res = Math.max(res, howFar(matrix, i, j));
            }
        }

        return res;
    }

    private int howFar(int[][] matrix, int x, int y) {
        if (ans[x][y] != -1) return ans[x][y];
        ans[x][y] = 1;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if (matrix[nx][ny] > matrix[x][y])
                ans[x][y] = Math.max(ans[x][y], howFar(matrix, nx, ny) + 1);
        }
        return ans[x][y];
    }
}
